package main

import "fmt"

func main() {
	nums := []int{1, 3, 2, 5, -1}
	quickSort(nums, 0, len(nums)-1)
	fmt.Println(nums)
}

func quickSort(nums []int, left, right int) {
	if left > right {
		return
	}
	partitionIndex := getPartition(nums, left, right)
	//找基准元素
	quickSort(nums, left, partitionIndex-1)
	quickSort(nums, partitionIndex+1, right)

}

func getPartition(nums []int, begin, end int) int {
	partitionIndex := begin
	partitionValue := nums[partitionIndex]
	left, right := begin, end
	for left <= right {
		for left <= right {
			//右边区间的数小于基准元素
			if nums[right] < partitionValue {
				nums[left] = nums[right]
				partitionIndex = right
				left++
				break
			}
			right--
		}
		for left <= right {
			//右边区间的数小于基准元素
			if nums[left] > partitionValue {
				nums[right] = nums[left]
				partitionIndex = left
				right--
				break
			}
			left++
		}
	}
	nums[partitionIndex] = partitionValue
	return partitionIndex
}
